{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Height Checker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #counting-sort #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #计数排序 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: heightChecker"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #高度检查器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 <strong>非递减</strong> 的高度顺序排成一行。</p>\n",
    "\n",
    "<p>排序后的高度情况用整数数组 <code>expected</code> 表示，其中 <code>expected[i]</code> 是预计排在这一行中第 <code>i</code> 位的学生的高度（<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>heights</code> ，表示 <strong>当前学生站位</strong> 的高度情况。<code>heights[i]</code> 是这一行中第 <code>i</code> 位学生的高度（<strong>下标从 0 开始</strong>）。</p>\n",
    "\n",
    "<p>返回满足<em> </em><code>heights[i] != expected[i]</code> 的 <strong>下标数量</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights =&nbsp;[1,1,4,2,1,3]\n",
    "<strong>输出：</strong>3 \n",
    "<strong>解释：</strong>\n",
    "高度：[1,1,<em><strong>4</strong></em>,2,<em><strong>1</strong></em>,<em><strong>3</strong></em>]\n",
    "预期：[1,1,<em><strong>1</strong></em>,2,<em><strong>3</strong></em>,<em><strong>4</strong></em>]\n",
    "下标 2 、4 、5 处的学生高度不匹配。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [5,1,2,3,4]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "高度：[<em><strong>5</strong></em>,<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>,<em><strong>4</strong></em>]\n",
    "预期：[<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>,<em><strong>4</strong></em>,<em><strong>5</strong></em>]\n",
    "所有下标的对应学生高度都不匹配。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>heights = [1,2,3,4,5]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "高度：[1,2,3,4,5]\n",
    "预期：[1,2,3,4,5]\n",
    "所有下标的对应学生高度都匹配。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= heights.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= heights[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [height-checker](https://leetcode.cn/problems/height-checker/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [height-checker](https://leetcode.cn/problems/height-checker/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,4,2,1,3]', '[5,1,2,3,4]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(i != j for i, j in zip(heights, sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum([x!=y for x,y in zip(heights,sorted(heights))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(x != y for x, y in zip(heights, sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        a=sorted(heights)\n",
    "        n=len(a)\n",
    "        b=0\n",
    "        for i in range(n):\n",
    "            if a[i]!=heights[i]:\n",
    "                b+=1\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected=sorted(heights)\n",
    "        bpp=0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i]!=expected[i]:\n",
    "                bpp+=1\n",
    "        return bpp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        return sum(1 for x, y in zip(heights, expected) if x != y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        i = -1\n",
    "        j = -1\n",
    "        count = 0\n",
    "        nm = []\n",
    "        nm.extend(heights)\n",
    "        nm.sort()\n",
    "        for x in range(len(heights)):\n",
    "            i += 1\n",
    "            j += 1\n",
    "            if heights[i] != nm[j]:\n",
    "                count += 1\n",
    "                \n",
    "           \n",
    "        return count            \n",
    "       \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum([1 for x, y in enumerate(sorted(heights)) if heights[x] != y ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        heights1 = sorted(heights)\n",
    "        s = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != heights1[i]:\n",
    "                s += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        # 最简单的思路：排序后跟原数组对比\n",
    "        nums = sorted(heights)\n",
    "        ans = 0\n",
    "        for i in range(len(heights)):\n",
    "            if (heights[i] != nums[i]):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        sorted_h = sorted(heights)\n",
    "        return len([i for i,h in enumerate(heights) if heights[i]!=sorted_h[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights) -> int:\n",
    "        st = sorted(heights)\n",
    "        err = 0\n",
    "        for n in range(len(heights)):\n",
    "            if heights[n] != st[n]:\n",
    "                err += 1\n",
    "        return err"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        return sum(a != b for a,b in zip(heights, expected))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected=sorted(heights)\n",
    "        return sum(1 for x,y in zip(heights,expected)if x!=y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        count = 0\n",
    "        res = copy.deepcopy(heights)\n",
    "        res.sort()\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != res[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        ans = 0\n",
    "        expected = sorted(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != expected[i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "\n",
    "        check = sorted(heights)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(len(check)):\n",
    "            if check[i] != heights[i]:\n",
    "                result += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        m = max(heights)\n",
    "        list = [0]*(m+1)\n",
    "        for i in heights:\n",
    "            list[i] += 1\n",
    "        ans = []\n",
    "        for i in range(len(list)):\n",
    "            for j in range(list[i]):\n",
    "                ans.append(i)\n",
    "        n = 0\n",
    "        for i in range(len(ans)):\n",
    "            if not ans[i] == heights[i]:\n",
    "                n += 1\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        n = len(heights)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if heights[i] != expected[i]:\n",
    "                cnt += 1\n",
    "        return cnt            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(i != j for i, j in zip(heights, sorted(heights)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def heightChecker(self, heights: List[int]) -> int:\r\n",
    "        expect = sorted(heights)\r\n",
    "        ans = 0\r\n",
    "        for i in range(len(heights)):\r\n",
    "            if heights[i] != expect[i]:\r\n",
    "                ans += 1\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        cnt = [0] * 101\n",
    "        for height in heights:\n",
    "            cnt[height] += 1\n",
    "        index = 0\n",
    "        count = 0\n",
    "        for i in range(101):\n",
    "            for j in range(cnt[i]):\n",
    "                if heights[index] != i:\n",
    "                    count += 1\n",
    "                index += 1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        required_seq = sorted(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != required_seq[i]:\n",
    "                res += 1\n",
    "\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        count = 0\n",
    "        for i, j in zip(heights, expected):\n",
    "            if i != j:\n",
    "                count +=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        res = sorted(heights)\n",
    "        count = 0\n",
    "        for i in range(len(heights)):\n",
    "            if res[i] != heights[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        count = 0\n",
    "        nm = []\n",
    "        nm.extend(heights)\n",
    "        nm.sort()\n",
    "        for x in range(len(heights)):\n",
    "            if heights[i] != nm[j]:\n",
    "                count += 1\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                continue\n",
    "        return count            \n",
    "       \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        m = max(heights)\n",
    "        list = [0]*(m+1)\n",
    "        for i in heights:\n",
    "            list[i] += 1\n",
    "        ans = []\n",
    "        for i in range(len(list)):\n",
    "            for j in range(list[i]):\n",
    "                ans.append(i)\n",
    "        n = 0\n",
    "        for i in range(len(ans)):\n",
    "            if not ans[i] == heights[i]:\n",
    "                n += 1\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        a = sorted(heights)\n",
    "        ans = 0\n",
    "        for i in range(len(a)):\n",
    "            if a[i] != heights[i]:ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = heights[:]\n",
    "        expected.sort()\n",
    "        count = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != expected[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        new=sorted(heights)\n",
    "        n=len(new)\n",
    "\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            if heights[i] !=new[i]:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected=sorted(heights)\n",
    "        m=0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i]!=expected[i]:\n",
    "                m=m+1\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        a=sorted(heights)\n",
    "        n=0\n",
    "        for i in range(len(heights)):\n",
    "            if a[i]!=heights[i]:\n",
    "                n=n+1\n",
    "        return n\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        nums = sorted(heights)\n",
    "        res = 0\n",
    "        for i, j in zip(nums, heights):\n",
    "            if i != j:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expect_heights = copy.deepcopy(heights)\n",
    "        expect_heights.sort()\n",
    "        index = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != expect_heights[i]:\n",
    "                index += 1\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        result = 0\n",
    "        for i in range(0,len(heights)):\n",
    "            if expected[i] != heights[i]:\n",
    "                result = result + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        ll=[]\n",
    "        nums = sorted(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] !=nums[i]:\n",
    "                ll.append(i)\n",
    "        return len(ll)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        n = len(heights)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if expected[i] != heights[i]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        count = 0\n",
    "        height = sorted(heights)\n",
    "        for i in range(len(heights)):\n",
    "            if height[i]!=heights[i]:\n",
    "                count = count+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        1.排序进行比较\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        a = heights\n",
    "        heights = sorted(heights)\n",
    "        lens = len(heights)\n",
    "\n",
    "        for i in range(lens):\n",
    "            if heights[i] != a[i]:\n",
    "                res = res + 1\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        temp = sorted(heights)\n",
    "        res = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i]!=temp[i]:\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(a != b for a,b in zip(heights, sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        cnt = 0\n",
    "        for a, b in zip(expected, heights):\n",
    "            cnt += 1 if a != b else 0\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(a != b for a, b in zip(heights, sorted(heights)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        return sum(1 for x, y in zip(heights, expected) if x != y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected=sorted(heights)\n",
    "        return sum(heights[i]!=expected[i] for i in range(len(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        target = heights.copy()\n",
    "        target.sort()\n",
    "\n",
    "        res = 0\n",
    "        for i in range(0, len(heights)):\n",
    "            if heights[i] != target[i] :\n",
    "                res = res + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum(i != j for i,j in zip(heights,sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        new = sorted(heights)\n",
    "        count = 0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != new[i]:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expect = sorted(heights)\n",
    "        res = 0\n",
    "        for i in range(len(expect)):\n",
    "            if heights[i] != expect[i]:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        tmp = sorted(heights)\n",
    "        k = 0\n",
    "        for i in range(len(heights)):\n",
    "            if tmp[i] != heights[i]:\n",
    "                k +=1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        s = []\n",
    "        for x in heights:\n",
    "            s.append(x)\n",
    "\n",
    "\n",
    "        temp =heights\n",
    "        temp.sort()\n",
    "        # for b in range(len(temp)):\n",
    "        #     for a in range(len(temp)-b-1):\n",
    "        #         if temp[a]>temp[a+1]:\n",
    "        #             d = temp[a+1]\n",
    "        #             temp[a+1] = temp[a]\n",
    "        #             temp[a]=d\n",
    "\n",
    "\n",
    "        print(s)\n",
    "        print(temp)\n",
    "        j=0\n",
    "        for i in range(len(heights)):\n",
    "            print(temp[i],heights[i])\n",
    "            if temp[i] != s[i]:\n",
    "                j+=1\n",
    "                print(\"####\")\n",
    "        print(j)\n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected = sorted(heights)\n",
    "        count = 0\n",
    "        \n",
    "        for i in range(len(heights)):\n",
    "            if heights[i] != expected[i]:\n",
    "                count += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        e = sorted(heights)\n",
    "        ans = 0\n",
    "        for i, j in zip(heights, e):\n",
    "            if i != j:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        \n",
    "        return sum(h1 != h2 for h1, h2 in zip(heights, sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        a=sorted(heights)\n",
    "        count=0\n",
    "        for i in range(len(heights)):\n",
    "            if heights[i]!=a[i]:\n",
    "                count+=1\n",
    "            else:\n",
    "                continue\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        re,expected=0,sorted(heights)\n",
    "        for i,j in zip(heights,expected):\n",
    "            if i!=j:re+=1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        expected=sorted(heights)\n",
    "        n = len(expected)\n",
    "        cnt=0\n",
    "        for i  in range(n):\n",
    "            if expected[i]!=heights[i]:\n",
    "                cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        if len(heights) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            heights_sort = heights.copy()\n",
    "            heights_sort.sort()\n",
    "            count = 0\n",
    "            for i in range(len(heights)):\n",
    "                if heights_sort[i] !=  heights[i]:\n",
    "                    count+=1\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        return sum( a != b for a,b in zip(heights, sorted(heights)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def heightChecker(self, heights: List[int]) -> int:\n",
    "        l=sorted(heights)\n",
    "        ans=0\n",
    "        for x,y in zip(heights,l):\n",
    "            if x!=y:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
